|
In mathematics, the Kolakoski sequence (named after William Kolakoski, who discussed it in 1965〔William Kolakoski, ''Self-Generating Runs, Problem 5304'', American Mathematical Monthly, vol. 72 (1965), p. 674〕) is an infinite sequence of symbols which is its own run-length encoding.〔 The initial terms of the sequence are: :1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,… Each symbol occurs in a "run" of either 1 or 2 consecutive terms, and writing down the lengths of these runs gives exactly the same sequence. It is the unique sequence with this property except for the same sequence with the initial 1 deleted.〔Pytheas Fogg (2002) p.93〕 ==Algorithm== The sequence may be generated by an algorithm that, in the ''i''th iteration, reads the value ''x''''i'' that has already been output as the ''i''th value of the sequence (or, if no such value has been output yet, sets ''x''''i'' = ''i''). Then, if ''i'' is odd, it outputs ''x''''i'' copies of the number 1, while if ''i'' is even, it outputs ''x''''i'' copies of the number 2. Thus, the first few steps of the algorithm are: #The first value has not yet been output, so set ''x''1 = 1, and output 1 copy of the number 1 #The second value has not yet been output, so set ''x''2 = 2, and output 2 copies of the number 2 #The third value ''x''3 was output as 2 in the second step, so output 2 copies of the number 1. #The fourth value ''x''4 was output as 1 in the third step, so output 1 copy of the number 2. etc. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kolakoski sequence」の詳細全文を読む スポンサード リンク
|